/**
 * Created With IntelliJ IDEA
 * Description:leetcode：236. 二叉树的最近公共祖先
 * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/">...</a>
 * User: DELL
 * Data: 2023-01-14
 * Time: 23:06
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
//题目规定：
//        树中节点数目在范围 [2, 10^5] 内。
//        -10^9 <= Node.val <= 10^9
//        所有 Node.val 互不相同 。
//        p != q
//        p 和 q 均存在于给定的二叉树中。
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root,p,q);
    }

    /**
     * 函数找到结点的val等于p的或q的时候，返回对应的结点
     * 当没有找到一个结点的val等于p的或q的时候，返回null
     */
    private TreeNode find(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        TreeNode leftNode = find(root.left,p,q);
        TreeNode rightNode = find(root.right,p,q);
        if (leftNode == null) {
            return rightNode;
        } else if (rightNode == null) {
            return leftNode;
        } else {
            return root;
        }
    }
}